import java.util.ArrayList;
import java.util.List;
/**
 * Deadlock stuff. :) 
 * @author dcreel121
 *
 */
public class Deadlock {

	private ArrayList<Position> staticDLs;
	
	private BoardElement[][] elements;
	private List<Goal> goals;
	private List<Position> boxes;	
	private Board board;

	public Deadlock(Board board) {
		this.board = board;
		this.staticDLs = new ArrayList<Position>();
		this.goals = board.getAllGoals();
		this.boxes = board.getBoxes();
		this.elements = removeBoxes(board.getElements());
		computeStaticDLs();
//		for (Position pos: this.staticDLs)
//		{
//			System.out.println(pos.toString());
//		}	
		
		
	}

	private BoardElement[][] removeBoxes(BoardElement[][] withBoxes) {

		BoardElement[][] noBoxes = new BoardElement[withBoxes.length][withBoxes[0].length];

        for(int i = 0; i < noBoxes.length; ++ i)
            for(int j = 0; j < noBoxes[0].length; ++ j)
                noBoxes[i][j] = withBoxes[i][j].copy();

		// Remove all boxes from the board
		for (Position box : boxes) {
			noBoxes[box.getX()][box.getY()] = BoardElement.EMPTY_FLOOR;
		}

		return noBoxes;
	}

	private void computeStaticDLs() {

		/*
		 * For each goal find every reachable spot by placing a box on the goal
		 * and "pulling" the box to every reachable spot.
		 */
		ArrayList<Position> reachable = new ArrayList<Position>();
		
		for (Position goal : goals) {
			for (Position p : findReachablePositions(goal))
				if (!reachable.contains(p)) {
					reachable.add(p);
				}
		}
		
		// Use reachable spots to find static deadlocks 
		for (int i = 0; i < elements.length; i++) {
			for (int j = 0; j < elements[i].length; j++) {
				
				Position cur = new Position(i, j);
				if (!reachable.contains(cur) && isWalkable(cur)) {
					staticDLs.add(cur);
				}
			}
		}		
	}

	private ArrayList<Position> findReachablePositions(Position goal) {

		boolean[][] visited = new boolean[elements.length][elements[0].length];
		ArrayList<Position> reachable = new ArrayList<Position>();

		// Note: In order to pull a box from a goal there must be two open spots in
		// the direction of pulling: one for the player and one for the box.

		Position box = new Position(goal.getX(), goal.getY());

		visited[goal.getX()][goal.getY()] = true;

		// Try pulling box up
		if (canMoveUp(box, visited)) {
			findReachableHelper(moveUp(box.copy()), reachable, visited.clone());
		}

		// Try pulling box left
		if (canMoveLeft(box, visited)) {
			findReachableHelper(moveLeft(box.copy()), reachable, visited.clone());
		}

		// Try pulling box down
		if (canMoveDown(box, visited)) {
			findReachableHelper(moveDown(box.copy()), reachable, visited.clone());
		}

		// Try pulling box right
		if (canMoveRight(box, visited)) {
			findReachableHelper(moveRight(box.copy()), reachable, visited.clone());
		}

		return reachable;
	}

	private void findReachableHelper(Position box, ArrayList<Position> reachable, boolean[][] visited) 
	{		
		reachable.add(box.copy());
		
		visited[box.getX()][box.getY()] = true;
		
		// Try pulling box up
		if (canMoveUp(box, visited)) {
			findReachableHelper(moveUp(box.copy()), reachable, visited.clone());
		}

		// Try pulling box left
		if (canMoveLeft(box, visited)) {
			findReachableHelper(moveLeft(box.copy()), reachable, visited.clone());
		}

		// Try pulling box down
		if (canMoveDown(box, visited)) {
			findReachableHelper(moveDown(box.copy()), reachable, visited.clone());
		}

		// Try pulling box right
		if (canMoveRight(box, visited)) {
			findReachableHelper(moveRight(box.copy()), reachable, visited.clone());
		}
	}
	
	private Position moveRight(Position p) {
		return new Position(p.getX(), p.getY()+1);
	}

	private Position moveDown(Position p) {
		return new Position(p.getX()+1, p.getY());
	}

	private Position moveLeft(Position p) {
		return  new Position(p.getX(), p.getY()-1); 
	}

	private Position moveUp(Position p) {
		return new Position(p.getX()-1, p.getY());
	}
	
	private boolean canMoveLeft(Position p, boolean[][] visited) {
		Position player = new Position(p.getX(), p.getY()-2);
		Position box = new Position(p.getX(), p.getY()-1); 
		if (isWalkable(player) && isWalkable(box) && !visited[box.getX()][box.getY()]) {
			return true;
		}
		return false;
	}
	
	private boolean canMoveRight(Position p, boolean[][] visited) {
		Position player = new Position(p.getX(), p.getY()+2);
		Position box = new Position(p.getX(), p.getY()+1);
		if (isWalkable(player) && isWalkable(box) && !visited[box.getX()][box.getY()]) {
			return true;
		}
		return false;
	}
	
	private boolean canMoveUp(Position p, boolean[][] visited) {
		Position player = new Position(p.getX()-2, p.getY());
		Position box = new Position(p.getX()-1, p.getY());
		if (isWalkable(player) && isWalkable(box) && !visited[box.getX()][box.getY()]) {
			return true;
		}
		return false;
	}
	
	private boolean canMoveDown(Position p, boolean[][] visited) {
		Position player = new Position(p.getX()+2, p.getY());
		Position box = new Position(p.getX()+1, p.getY());
		if (isWalkable(player) && isWalkable(box) && !visited[box.getX()][box.getY()]) {
			return true;
		}
		return false;
	}
	
	private boolean isWalkable(Position p) {
		if (p.getX() < 0 || p.getX() > elements.length-1 || 
				p.getY() < 0 || p.getY() > elements[0].length-1) {
			return false;
		}
		BoardElement e = elements[p.getX()][p.getY()];
		if (e == BoardElement.EMPTY_FLOOR || e == BoardElement.GOAL
				|| e == BoardElement.PLAYER) {
			return true;
		}
		return false;
	}
	
	public boolean isDeadlockFor(Board board, Position box)
	{
		this.board = board;
		//static
		if (staticDLs.contains(box))
		{
			return true;
		}
		//dynamic
		return isDynamicDeadlockFor(box, new ArrayList<Position>());		
	}
	
	private boolean isDynamicDeadlockFor(Position box, ArrayList<Position> alreadyChecked) 
	{
		BoardElement bottom = board.getElement(board.getPositionBottomOf(box));
		BoardElement top = board.getElement(board.getPositionTopOf(box));
		BoardElement left = board.getElement(board.getPositionLeftOf(box));
		BoardElement right = board.getElement(board.getPositionRightOf(box));

		boolean bottomFilled = false;
		boolean topFilled = false;
		boolean leftFilled = false;
		boolean rightFilled = false;

		//bottom
		if (bottom == BoardElement.BOX
				|| bottom == BoardElement.BOX_ON_GOAL) 
		{
			if (!alreadyChecked.contains(board.getPositionBottomOf(box)))
			{				
				ArrayList<Position> childAldreadyChecked = new ArrayList<Position>(alreadyChecked);
				childAldreadyChecked.add(board.getPositionBottomOf(box));
				//check whether the neigbour box can be pushed or not
				bottomFilled = isDynamicDeadlockFor(board.getPositionBottomOf(box), childAldreadyChecked);
			}
			else
			{
				bottomFilled = true;
			}			
		}
		else if (bottom == BoardElement.WALL)
		{
			bottomFilled = true;
		}
		//top
		if (top == BoardElement.BOX
				|| top == BoardElement.BOX_ON_GOAL) 
		{
			if (!alreadyChecked.contains(board.getPositionTopOf(box)))
			{				
				ArrayList<Position> childAldreadyChecked = new ArrayList<Position>(alreadyChecked);
				childAldreadyChecked.add(board.getPositionTopOf(box));
				//check whether the neigbour box can be pushed or not
				topFilled = isDynamicDeadlockFor(board.getPositionTopOf(box), childAldreadyChecked);
			}
			else
			{
				topFilled = true;
			}
		}
		else if (top == BoardElement.WALL)
		{
			topFilled = true;
		}
		
		if (left == BoardElement.BOX
				|| left == BoardElement.BOX_ON_GOAL) 
		{
			if (!alreadyChecked.contains(board.getPositionLeftOf(box)))
			{				
				ArrayList<Position> childAldreadyChecked = new ArrayList<Position>(alreadyChecked);
				childAldreadyChecked.add(board.getPositionLeftOf(box));
				//check whether the neigbour box can be pushed or not
				leftFilled = isDynamicDeadlockFor(board.getPositionLeftOf(box), childAldreadyChecked);
			}
			else
			{
				leftFilled = true;
			}
		}
		else if (left == BoardElement.WALL)
		{
			leftFilled = true;
		}
		
		if (right == BoardElement.BOX
				|| right == BoardElement.BOX_ON_GOAL) 
		{
			if (!alreadyChecked.contains(board.getPositionRightOf(box)))
			{				
				ArrayList<Position> childAldreadyChecked = new ArrayList<Position>(alreadyChecked);
				childAldreadyChecked.add(board.getPositionRightOf(box));
				//check whether the neigbour box can be pushed or not
				rightFilled = isDynamicDeadlockFor(board.getPositionRightOf(box), childAldreadyChecked);
			}
			else
			{
				rightFilled = true;
			}
		}
		else if (right == BoardElement.WALL)
		{
			rightFilled = true;
		}

		if ((bottomFilled && leftFilled) || (bottomFilled && rightFilled)
				|| (topFilled && leftFilled) || (topFilled && rightFilled)) {
			return true;
		}
		return false;
	}

	public ArrayList<Position> getStaticDLs() {
		return staticDLs;
	}
	
	
}
